package com.sjf.day04.binarysearchnorecursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 二分查找(非递归实现)
 *
 * @author <huangtang>
 * @since 2022/1/14 14:36
 **/
public class BinarySearchNoRecur {

    public static void main(String[] args) {
        int[] arr = {3, 66, 75, 99, 108, 347, 347, 523};
        System.out.println(Collections.singletonList(binarySearch(arr, 347)));
    }

    /**
     * 二分查找算法
     *
     * @param arr    查找数组
     * @param target 查找的数值
     * @return 返回对应下标，-1表示没有找到
     */
    public static List<Integer> binarySearch(int[] arr, int target) {
        List<Integer> list = new ArrayList<>();
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                //向左边找
                int temp = mid - 1;
                while (temp > 0 && arr[temp] == target) {
                    list.add(temp--);
                }
                list.add(mid); //中值加入
                temp = mid + 1;
                //向右边找
                while (temp < arr.length - 1 && arr[temp] == target) {
                    list.add(temp++);
                }

                return list;//找到
            } else if (target < arr[mid]) { //target小于中值，则向左查找
                right = mid - 1;
            } else if (target > arr[mid]) { //target大于中值，则向右查找
                left = mid + 1;
            }
        }
        return Collections.singletonList(-1);
    }

}
